package com.itheima.priorityqueue;

import com.itheima.queue.Queue;

/**
 * 基于有序数组实现
 *
 * @FileName PriorityQueue2
 * @Description
 * @Author Sword
 * @date 2025-05-15
 **/
public class PriorityQueue2<E extends Priority> implements Queue<E> {

    Priority[] array;
    int size;

    // O(n)
    @Override
    public boolean offer(E valvue) {
        if (isFull()) {
            return false;
        }

        insert(valvue);
        size++;
        return true;
    }

    private void insert(E valvue) {
        int i = size - 1;

        while (i >= 0 && array[i].priority() > valvue.priority()) {
            array[i + 1] = array[i];
            i--;
        }
        array[i + 1] = valvue;
    }

    // O(1)
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E e = (E) array[size - 1];
        array[--size] = null;   //help GC
        return e;
    }

    // O(1)
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }

        return (E) array[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
